import java.util.*;

public class Test {
    /*
    题目1：有效三角形个数
     */
    // 三角形任意两边之和大于第三边
    // 如果这三边排好序的话，只需考虑两条小边之和是否大于最大边！
    public int triangleNumber(int[] nums) {
        Arrays.sort(nums);

        int count = 0;
        int n = nums.length;
        for (int i = n - 1; i >= 2; i--) {
            int left = 0;
            int right = i - 1;

            while (left < right) {
                int sum = nums[left] + nums[right];
                if (sum > nums[i]) {
                    count += right - left;
                    right--;
                } else {
                    left++;
                }
            }
        }
        return count;
    }

    /*
    题目2：长度最小的子数组
     */
    public int minSubArrayLen(int target, int[] nums) {
        // 利用 和 的单调性
        int n = nums.length;
        int sum = 0;
        int len = n + 1;

        for (int left = 0, right = 0; right < n; right++) {
            sum += nums[right];
            while (sum >= target) {
                len = Math.min(len, right - left + 1);
                sum -= nums[left++];

            }
        }
        return len == n + 1 ? 0 : len;
    }

    /*
    题目3：无重复字符的最长子串
     */
    public int lengthOfLongestSubstring(String ss) {
        char[] s = ss.toCharArray();
        int[] hash = new int[128];
        int n = s.length;
        int len = 0;

        for (int left = 0, right = 0; right < n; right++) {
            hash[s[right]]++;
            while (hash[s[right]] > 1) {
                hash[s[left++]]--;
            }
            len = Math.max(len, right - left + 1);
        }

        return len;
    }

    /*
    题目4：最大连续1的个数 Ⅲ
     */
    public int longestOnes(int[] nums, int k) {
        int n = nums.length;
        int len = 0;
        int count = 0;

        for (int left = 0, right = 0; right < n; right++) {
            if (nums[right] == 0) {
                count++;
            }
            while (count > k) {
                // 即便条件不成立，也会执行，也就是left++
                if (nums[left++] == 0) {
                    count--;
                }
            }

            len = Math.max(len, right - left + 1);
        }
        return len;
    }

    /*
    题目5：将 x 减到 0 的最小操作数
     */
    public int minOperations(int[] nums, int x) {
        int sum = 0;
        int n = nums.length;

        for (int i = 0; i < n; i++) {
            sum += nums[i];
        }

        int tg = sum - x;
        if (tg < 0) {
            return -1;
        }

        int s = 0;
        int len = -1;

        for (int left = 0, right = 0; right < n; right++) {
            s += nums[right];

            while (s > tg) {
                s -= nums[left++];
            }
            if (s == tg) {
                len = Math.max(len, right - left + 1);
            }
        }
        return len == -1 ? len : n - len;
    }

    /*
    题目 6：水果篮子
     */
    public int totalFruit(int[] f) {
        Map<Integer, Integer> map = new HashMap<>();

        int n = f.length;
        int len = 0;

        for (int left = 0, right = 0; right < n; right++) {
            int in = f[right];
            map.put(in, map.getOrDefault(in, 0) + 1);
            while (map.size() > 2) {
                int out = f[left];
                map.put(out, map.get(out) - 1);
                if (map.get(out) == 0) {
                    map.remove(out);
                }
                left++;
            }

            len = Math.max(len, right - left + 1);

        }
        return len;
    }

    public static void main1(String[] args) {

        String str = "asdbnxxs";
        String str1 = str.substring(0, 1);
        System.out.println(str1.equals("a"));
    }

    /*
    题目7：串联所有单词的子串
     */
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> list = new LinkedList<>();
        int n = words.length;
        int len = words[0].length();
        int m = s.length();

        Map<String, Integer> map1 = new HashMap<>();

        for(String ss : words){
            map1.put(ss, map1.getOrDefault(ss, 0) + 1);
        }

        for(int i = 0; i < len; i++){
            Map<String, Integer> map2 = new HashMap<>();
            for(int left = i, right = i, count = 0; right + len <= m; right += len){
                String str = s.substring(right, right + len);
                map2.put(str, map2.getOrDefault(str, 0) + 1);

                if(map2.get(str) <= map1.getOrDefault(str, 0)){
                    count++;
                }

                // 出窗口
                if((right - left + 1) > n * len){
                    String str1 = s.substring(left, left + len);


                    if(map2.get(str1) <= map1.getOrDefault(str1, 0)){
                        count--;
                    }
                    map2.put(str1, map2.get(str1) - 1);
                    left += len;
                }
                if(count == n){
                    list.add(left);
                }
            }
        }
        return list;
    }

    public static void main(String[] args) {
        String s = "wordgoodgoodgoodbestword";
        String[] ss = {"word","good","best","good"};
        List<Integer> list = findSubstring(s, ss);
    }

}